Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра
С А П Р
З в і т
про виконання
лабораторної роботи №1
на тему:
«ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ»
З курсу:
«Організація баз даних і знань»
Виконав:
ст. гр. КН-4
Львів 2007р.
1. МЕТА РОБОТИ
Розглянути органiзацiю i ведення файлiв послiдовного доступу; набути практичнi навички у програмуваннi алгоритмiв роботи з файлами послiдовного доступу.
2. ТЕОРЕТИЧНI ВIДОМОСТI
Будь-який обмiн даними передбачає присутнiсть джерела iнформацiї, каналу передачi та її приймача. У випадку обмiну даними мiж програмою i периферiйним пристроєм одним кiнцем каналу обмiну даними завжди є оперативна пам’ять ПЕОМ. Другий кiнець цього каналу у бiльшостi мов програмування визначений як файл.
Поняття файла достатньо широке. Це може бути комунiкацiйний порт, пристрiй друку. У данiй роботi розглядається файл даних.
Одним iз головних чинникiв, що впливає на продуктивнiсть програм, якi взаємодiють iз базою даних, є спосiб зберiгання i доступу до файлiв даних: послiдовний, iндексно-послiдовний, індексно-довiльний, прямий, хешування.
Усi методи розглядаються за двома критерiями:
1. Ефективнiсть доступу - величина, обернена середнiй кiлькостi фiзичних звертань, необхiдних для логiчного доступу, тобто запиту конкретного запису бази даних. Фiзичнi звертання забезпечують задоволення запиту. Наприклад, якщо для пошуку потрiбного запису система звертається до двох записiв, то ефективнiсть доступу дорiвнює 0,5.
2. Ефективнiсть зберiгання - величина, обернена середнiй кiлькостi байтiв поля вторинної пам’ятi, яка необхiдна для зберiгання одного байта вхiдних даних.
Крiм вхiдних даних, пам’ять займають таблицi, керуюча iнформацiя, вiльна пам’ять, яка резервується для розширень, i дiлянка, яка не використовується через фрагментацiю
2.1. ДОСТУП ДО ЗАПИСІВ
Записи у простому послiдовному файлi доступнi лише послiдовно один за одним. Наприклад, можна звернутися до n-го запису тiльки пiсля звертання до 1,2,...,n-1 записiв. Для того, щоб видалити запис з файла, необхiдно створити копiю файла, у якiй цей запис є вiдсутнiм; для того, щоб помiстити запис у файл, також необхiдно створити копiю файла, у яку цей новий запис входить. Щоб змiнити хоча б одне з полiв у записi, необхiдно створити копiю файла, який мiститиме модифiкований запис. При послiдовному методi доступу значення ключiв фiзичних записiв знаходяться у логiчнiй послiдовностi.
2.1.1. Ефективнiсть доступу. Нехай вибрано один фiзичний запис, i належить вибрати iнший з бiльшим значенням ключа. У найгiршому випадку для вибору потрiбного запису необхiдно переглянути всi записи бази даних, а у кращому достатньо вибрати наступний запис. Для того, щоб виявити необхiдний запис у послiдовному файлi, який складається з N записiв, необхiдно переглянути у середньому N/2 записiв. Це пояснюється так. Нехай здiйснюється достатньо багато випробовувань, пов’язаних iз пошуком у послiдовному файлi випадково вибраних значень ключа. Причому кожний пошук починається з першого запису файла. Тодi для виявлення шуканого запису потрiбно переглянути у середньому половину загальної кiлькостi записiв.
2.1.2. Ефективнiсть зберiгання. Ефективнiсть використання пам'ятi близька до 100%. Зберiгання фiзичних записiв у логiчнiй послiдовностi можна використовувати для прискорення доступу, якщо перед звертанням до власне записiв бази даних перевiряти значення ключiв.
2.1.3 Алгоритм вставляння запису
<зчитати номер запису, який потрiбно вставити><m>
<зчитати данi><str>
<вiдкрити два файли, файл А - для читання, файл B - для зберiгання модифiкованої iнформацiї>
i:=1
доки не кiнець файла А
якщо m<>i
тодi <зчитати з А, записати в B>
i:=i+1
iнакше <записати у В str>
якщо m>=i
тодi <записати в В str>
<закрити файли А, В>
<змiнити iм'я з В на А>
2.1.4. Алгоритм модифiкацiї записiв
<зчитати номер запису, який пот...
